home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / tcisam.zip / IDELETE.C < prev    next >
Text File  |  1987-08-15  |  6KB  |  195 lines
  1. /*
  2.  * IDELETE.C - delete a record
  3.  *
  4.  *                      Copyright (c) 1987, Jim Mischel
  5.  */
  6.  
  7. #include "inxdefs.h"
  8.  
  9. /*
  10.  * idelete() - remove the current record from the data stream.  The data
  11.  * record is not actually removed from the file and the index record is not
  12.  * removed from the index file.  The index pointers are adjusted so that
  13.  * they skip over the index for this record.
  14.  * Returns 0 if successful, error status otherwise.  If the key at 'source'
  15.  * is not the same as the key in the current data record, I_INVKEY is
  16.  * returned and no action is taken.  Since the only integrity check
  17.  * made is a simple key comparison, if duplicate keys are permitted, it
  18.  * is possible to delete the wrong record.
  19.  */
  20. int idelete(void *d, void *src)
  21. {
  22.   register df_rec *db_control = (df_rec *)d;
  23.   char *source = (char *)src;
  24.   register inx_rec *irec;
  25.   inx_rec save_inx_rec;
  26.   long save_inx_ptr;
  27.  
  28.   /* see if record has already been deleted */
  29.   if (db_control->df_flags & DF_DELETE)
  30.     return(ierror(I_INVKEY));
  31.  
  32.   /* see if keys are equal */
  33.   if ((*db_control->df_cmp)((source+db_control->df_key_offset),
  34.                             db_control->df_key_ptr))
  35.     return(ierror(I_INVKEY));           /* error: keys not equal */
  36.  
  37.   /*
  38.    * There are 3 cases to worry about:
  39.    * 1. The node is a leaf
  40.    * 2. The node has only 1 son
  41.    * 3. The node has 2 sons
  42.    */
  43.  
  44.   /* setup a pointer to the current index record */
  45.   irec = &db_control->df_inx_buff;
  46.   memcpy(&save_inx_rec,irec,sizeof(inx_rec));   /* copy current index rec */
  47.   save_inx_ptr = db_control->df_inx_ptr;        /* save current index pointer */
  48.  
  49.   if ((irec->if_flags & RTHRD) && (irec->if_flags & LTHRD)) {
  50.  
  51.   /*
  52.    * the node has no descendents (leaf)
  53.    */
  54.     if (iread_inx(db_control,irec->if_parent))  /* get parent node */
  55.       return(ierrno);
  56.  
  57.     if (irec->if_left_node == save_inx_ptr) {   /* node is a left son */
  58.       irec->if_left_node = save_inx_rec.if_left_node;
  59.       irec->if_flags |= ((save_inx_rec.if_flags & BTHRD) | LTHRD);
  60.     }
  61.     else {              /* node is a right son */
  62.       irec->if_right_node = save_inx_rec.if_right_node;
  63.       irec->if_flags |= ((save_inx_rec.if_flags & ETHRD) | RTHRD);
  64.     }
  65.     if (iwrite_inx(db_control,irec,db_control->df_inx_ptr))
  66.       return(ierrno);
  67.   }
  68.   else if ((irec->if_flags & LTHRD) || (irec->if_flags & RTHRD)) {
  69.  
  70.   /*
  71.    * the node has only one son
  72.    */
  73.     long node_ptr;
  74.     int son;
  75.  
  76.     if (irec->if_flags & RTHRD)
  77.       node_ptr = irec->if_left_node;
  78.     else
  79.       node_ptr = irec->if_right_node;
  80.  
  81.     /* adjust parent node */
  82.     if (iread_inx(db_control,irec->if_parent))
  83.       return(ierrno);
  84.  
  85.     if (irec->if_left_node == save_inx_ptr) {   /* left son */
  86.       son = -1;
  87.       irec->if_left_node = node_ptr;
  88.     }
  89.     else {                                      /* right son */
  90.       son = 1;
  91.       irec->if_right_node = node_ptr;
  92.     }
  93.  
  94.     if (iwrite_inx(db_control,irec,db_control->df_inx_ptr))
  95.       return(ierrno);
  96.  
  97.     /* adjust only son */
  98.     if (iread_inx(db_control,node_ptr))
  99.       return(ierrno);
  100.     if (irec->if_right_node == save_inx_ptr)
  101.       irec->if_right_node = save_inx_rec.if_parent;
  102.     else if (irec->if_left_node == save_inx_ptr)
  103.       irec->if_left_node = save_inx_rec.if_parent;
  104.     irec->if_parent = save_inx_rec.if_parent;
  105.     if (iwrite_inx(db_control,irec,db_control->df_inx_ptr))
  106.       return(ierrno);
  107.  
  108.     /* adjust inorder successor/predecessor */
  109.     if (son == -1) {
  110.       if (iget_prev(db_control,&save_inx_rec))
  111.         return(ierrno);
  112.       irec->if_right_node = save_inx_ptr;
  113.     }
  114.     else {
  115.       if (iget_next(db_control,&save_inx_rec))
  116.         return(ierrno);
  117.       irec->if_left_node = save_inx_ptr;
  118.     }
  119.     if (iwrite_inx(db_control,irec,db_control->df_inx_ptr))
  120.       return(ierrno);
  121.   }
  122.   else {
  123.   /*
  124.    * the node has two sons
  125.    */
  126.     inx_rec save_parent,
  127.             save_prev;
  128.     long save_prev_ptr;
  129.  
  130.     if (iread_inx(db_control,irec->if_parent))  /* get parent node */
  131.       return(ierrno);
  132.     memcpy(&save_parent,irec,sizeof(inx_rec));  /* and save it */
  133.  
  134.     /*
  135.      * the deleted node will be replaced by its inorder predecessor
  136.      */
  137.  
  138.     if (iget_prev(db_control,&save_inx_rec))
  139.       return(ierrno);
  140.     memcpy(&save_prev,irec,sizeof(inx_rec));    /* and save it */
  141.     save_prev_ptr = db_control->df_inx_ptr;
  142.  
  143.     /*
  144.      * adjust the parent node to point to the replacement
  145.      */
  146.     if (save_parent.if_right_node == save_inx_ptr)      /* right son */
  147.       save_parent.if_right_node = save_prev_ptr;
  148.     else                                                /* left son */
  149.       save_parent.if_left_node = save_prev_ptr;
  150.     if (iwrite_inx(db_control,&save_parent,save_inx_rec.if_parent))
  151.       return(ierrno);
  152.  
  153.     /* update predecessor's parent */
  154.     if (iread_inx(db_control,save_prev.if_parent))
  155.       return(ierrno);
  156.     if (save_prev.if_flags & LTHRD)
  157.       irec->if_flags |= RTHRD;
  158.     else
  159.       irec->if_right_node = save_prev.if_left_node;
  160.     if (iwrite_inx(db_control,irec,db_control->df_inx_ptr))
  161.       return(ierrno);
  162.  
  163.     /* update predecessor's left son (if it exists) */
  164.     if (!(save_prev.if_flags & LTHRD)) {
  165.       if (iread_inx(db_control,save_prev.if_left_node))
  166.         return(ierrno);
  167.       irec->if_parent = save_prev.if_parent;
  168.       if (iwrite_inx(db_control,irec,db_control->df_inx_ptr))
  169.         return(ierrno);
  170.     }
  171.  
  172.     /* now update the replacement node */
  173.     save_prev.if_parent = save_inx_rec.if_parent;
  174.     save_prev.if_right_node = save_inx_rec.if_right_node;
  175.     if (save_inx_rec.if_left_node != save_prev_ptr) {
  176.       save_prev.if_left_node = save_inx_rec.if_left_node;
  177.       save_prev.if_flags = 0;
  178.     }
  179.     else {
  180.       save_prev.if_flags &= ~(RTHRD | ETHRD);
  181.     }
  182.     if (iwrite_inx(db_control,&save_prev,save_prev_ptr))
  183.       return(ierrno);
  184.  
  185.     /* get inorder successor and update its left thread pointer */
  186.     if (iget_next(db_control,&save_inx_rec))
  187.       return(ierrno);
  188.     irec->if_left_node = save_prev_ptr;
  189.     if (iwrite_inx(db_control,irec,db_control->df_inx_ptr))
  190.       return(ierrno);
  191.   }
  192.   db_control->df_flags |= DF_DELETE;    /* flag record as deleted */
  193.   return(0);
  194. } /* idelete */
  195.